/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年12月12日
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <stack>
using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int min_res = INT_MAX;
    TreeNode* pre_node = NULL;
    
public:
    int minDiffInBST(TreeNode* root) {
        inoder_search(root);
        return min_res;
    }

    void inoder_search(TreeNode *root){
        if(!root){
            return;
        }

        if(root->left){
            inoder_search(root->left);
        }
        if(pre_node != NULL){
            min_res = min(min_res, root->val - pre_node->val);
        }
        pre_node = root;

        if(root->right){
            inoder_search(root->right);
        }
    }
};


class Solution {
private:
    int min_res = INT_MAX;
public:
    int minDiffInBST(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode *p = root;
        TreeNode *pre = NULL;

        while(!s.empty() || p){
            while(p){
                s.push(p);
                p = p->left;
            }

            if(!s.empty()){
                p = s.top();
                if(pre){
                    min_res = min(min_res, p->val - pre->val);
                }

                pre = p;
                s.pop();
                p = p->right;
            }
        }

        return min_res;
    }
};
